[이코테-정렬]_두 배열의 원소 교체
💯 solving-algo | March 28, 2021
문제 설명
두 개의 A, B 배열에서 K 만큼 두 배열의 값을 교환해 A의 배열을 최대로 만드는 문제
My Solution
import heapq
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# 힙의 자료형의 특징을 이용해 sort()연산 두번을 없앰
# a.sort()
# b.sort()
for i in range(k):
min_number = heapq.heappop(a)
max_number = b.pop()
a.append(max_number)
print(sum(a))문제 풀이
- 처음에는 큐의
popleft()메소드를 이용해 풀려고 하였지만, O(nlongn)의 복잡도를 가진sort()를 2번 진행해야 한다는 점에서 좀 더 나은 자료형을 생각해보다heap를 이용해 풀었다. - heap 자료형은 파이썬에서 최소 힙이 기본 값이며, 항상 첫 번째 값은 가장 작은 값을 보장받는다는 점에서 효율적으로 문제를 풀었던 거 같다. 결론적으로
sort()연산 2번을 없앤셈
이코테 풀이
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort() # 배열 A는 오름차순 정렬 수행
b.sort(reverse=True) # 배열 B는 내림차순 정렬 수행
# 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for i in range(k):
# A의 원소가 B의 원소보다 작은 경우
if a[i] < b[i]:
# 두 원소를 교체
a[i], b[i] = b[i], a[i]
else: # A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
break
print(sum(a))문제를 풀고 나서 알게 된 사실
나의 풀이 방법은 B의 원소 값이 A의 원소 값보다 항상 클 시 적용되는 풀이었다. B의 원소가 A의 원소보다 작다면 오히려 기존 A의 원소 값보다 작아지기 때문에… 다음 번에 문제를 풀때는 조금 더 오랜 고민이 필요할 것 같다.
